#pragma once

#include "martino.giovanelli.h"
#include "../common/basetypes.h"
#include "../common/MathUtils.h"
#include "../common/ProblemCommons.h"
#include "../common/BigNumber.h"

#include "math.h"
#include "assert.h"


#include <vector>
#include <iostream>

bool MartinoGiovanelli::Init(Register& o_register)
{
	m_name = "MARTINO GIOVANELLI";

	REGISTER_FUNC(MartinoGiovanelli, 1);
	REGISTER_FUNC(MartinoGiovanelli, 2);
	REGISTER_FUNC(MartinoGiovanelli, 3);
	REGISTER_FUNC(MartinoGiovanelli, 4);
	REGISTER_FUNC(MartinoGiovanelli, 5);
	REGISTER_FUNC(MartinoGiovanelli, 6);
	REGISTER_FUNC(MartinoGiovanelli, 7);
	REGISTER_FUNC(MartinoGiovanelli, 8);
	REGISTER_FUNC(MartinoGiovanelli, 9);
	REGISTER_FUNC(MartinoGiovanelli, 10);
	REGISTER_FUNC(MartinoGiovanelli, 11);
	//REGISTER_FUNC(MartinoGiovanelli, 12);
	REGISTER_FUNC(MartinoGiovanelli, 13);
	REGISTER_FUNC(MartinoGiovanelli, 14);
	REGISTER_FUNC(MartinoGiovanelli, 16);
	REGISTER_FUNC(MartinoGiovanelli, 20);
	REGISTER_FUNC(MartinoGiovanelli, 25);
	//REGISTER_FUNC(MartinoGiovanelli, 48);

	return true;
}

namespace GiovaMath
{

}

/*
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.
The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
*/
RetType MartinoGiovanelli::Problem1()
{
	RetType sum = 0;

	for(UInt i = 999; i > 0; --i)
		if( i % 3 == 0 || i % 5 == 0)
			sum += i;

	return sum;
}

/*
Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.
*/
RetType MartinoGiovanelli::Problem2()
{
	RetType sum = 0;
	UInt lastNum = 1;
	UInt prevNum = 0;

	while(lastNum < 4000000)
	{
		sum += (lastNum % 2 == 0) ? lastNum : 0;
		UInt temp = lastNum;
		lastNum += prevNum; 
		prevNum = temp;
	}

	return sum;
}

/*
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
*/
RetType MartinoGiovanelli::Problem3()
{
	RetType number = 600851475143;
	RetType maxDivisor = 0;
	UInt32 divisor = 2;

	do
	{
		if (number % divisor == 0)
			number /= divisor;
		else
		{
			if (math::IsPrime(++divisor))
				maxDivisor = divisor;
		}
	}
	while (number != 1);

	return maxDivisor;
}


/*
A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.

Find the largest palindrome made from the product of two 3-digit numbers.
*/
RetType MartinoGiovanelli::Problem4()
{
	UInt32 temp = 0, max = 0;

	for (int i = 999; i > 99; --i)
	{
		for (int j = 999; j > 99; --j)
		{
			temp = i * j;
			if(math::IsPalindrome(temp))
			{
				if(temp > max)
					max = temp;
			}
		}
	}

	return max;
}

/*
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
*/
RetType MartinoGiovanelli::Problem5()
{
	RetType lastNum = 0;
	bool find = true;

	do 
	{
		find = true;
		lastNum += 20;	

		for(int i = 19; i > 1; --i)
		{
			if(lastNum % i != 0)
			{
				find = false;
				//break;			// wtf ???
				i = 0;				// hack
			}

		}

	} while (!find);

	return lastNum;
}


template<UInt32 N>
struct sumOfTheSquares
{
	static UInt32 const value = sumOfTheSquares<N-1>::value + (N * N);
};

template<>
struct sumOfTheSquares<0>
{
	static UInt32 const value = 0;
};

template<UInt32 N>
struct sum
{
	static UInt32 const value = sum<N-1>::value + N;
};

template<>
struct sum<0>
{
	static UInt32 const value = 0;
};

/*
The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + ... + 10^2 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025  385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
*/
RetType MartinoGiovanelli::Problem6()
{
	return (sum<100>::value * sum<100>::value) - sumOfTheSquares<100>::value;
}

/*
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
*/
RetType MartinoGiovanelli::Problem7()
{

	UInt32 primeCount = 1;
	UInt32 nextNum = 1;

	while(primeCount < 10001)
	{
		nextNum += 2;
		if(math::IsPrime(nextNum))
			++primeCount;
	}

	return nextNum;
}

inline bool containZero(const char* idx, UInt counts)
{
	for(UInt i = 0; i < counts; ++i)
		if( idx[i] == '0' )
			return true;

	return false;
}

inline bool containZero(const int* idx, UInt counts)
{
	for(UInt i = 0; i < counts; ++i)
		if( idx[i] == 0 )
			return true;

	return false;
}

inline int asciiToInt(const char c)
{
	return (int)c - 48;
}

/*
Find the greatest product of five consecutive digits in the 1000-digit number.
*/
RetType MartinoGiovanelli::Problem8()
{
	const char buffer[] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

	int i = 5;
	int curMaxIdx = 0;

	while(i < 995)
	{
		if(buffer[i] < buffer[curMaxIdx])
		{
			++i;
		}
		else if(buffer[i] > buffer[curMaxIdx])
		{
			if(!containZero(&buffer[i],4))
			{
				curMaxIdx = i;
				i += 5;
			}
			else
				++i;
		}
		else
		{
			UInt j = 1;
			while(j < 4)
			{
				if(buffer[i+j] == buffer[curMaxIdx+j])
				{
					++j;
				}
				else if(buffer[i+j] > buffer[curMaxIdx+j])
				{
					if(!containZero(&buffer[i],5))
					{
						curMaxIdx = i;
						j = 4;
					}
					break;
				}
				else
				{
					break;
				}
			}
			i += j;
		}

	}

	return asciiToInt(buffer[curMaxIdx + 0]) *
		   asciiToInt(buffer[curMaxIdx + 1]) *
		   asciiToInt(buffer[curMaxIdx + 2]) *
		   asciiToInt(buffer[curMaxIdx + 3]) *
		   asciiToInt(buffer[curMaxIdx + 4]);

}

/*
A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,

a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
*/
RetType MartinoGiovanelli::Problem9()
{

	// Euclid's formula
	// http://en.wikipedia.org/wiki/Pythagorean_triple
	UInt a, b, c;

	// n < m
	// a = m^2 - n^2
	// b = 2 * m * n
	// c = m^2 + n^2

	// NOTE:
	// max(b) = 499			NOTE: a < b < c
	// b/2 = 250 = m * n
	// max(n) = 16
	// min(m) = n + 1		NOTE: n < m
	// max(m) = 250 / n

	for(UInt n = 1; n < 16; ++n)
	{
		for(UInt m = n + 1; m < (250 / n); ++m)
		{
			a = m * m - n * n;
			b = 2 * m * n;
			c = m * m + n * n;

			if(a + b + c == 1000)
				return a * b * c; 
		}
	}

	assert(false); // error

	return 0;
}

/*template<UInt N, UInt D>
struct restTest
{
	static const bool value = ((N % D) != 0) && restTest<N,D-1>::value;
};

template<UInt N>
struct restTest<N, 1>
{
	static const bool value = true;
};

template<UInt N>
struct prime
{
	static const bool value = restTest<N,(N-1)>::value;
};

template<> struct prime<2>{ static const bool value = true; };
template<> struct prime<1>{ static const bool value = false; };
template<> struct prime<0>{ static const bool value = false; };

template<UInt N, bool B>
struct sumNPrimeHelper { static const UInt value = 0; };

template<UInt N>
struct sumNPrimeHelper<N, true> { static const UInt value = N; };

template<UInt N>
struct sumNPrimeHelper<N, false> { static const UInt value = 0; };

template<UInt N>
struct sumNPrime { static const UInt value = sumNPrimeHelper<N, prime<N>::value>::value + sumNPrime<N-1>::value; };

template<>
struct sumNPrime<2> { static const UInt value = 2; };
template<>
struct sumNPrime<1> { static const UInt value = 0; };
template<>
struct sumNPrime<0> { static const UInt value = 0; };*/

RetType MartinoGiovanelli::Problem10()
{
	//return sumNPrime<2000000>::value; // fail for now

	RetType primeSum = 2;
	UInt32 nextNum = 3;

	while(nextNum < 2000000)
	{
		if(math::IsPrime(nextNum))
			primeSum += nextNum;
		nextNum += 2;
	}

	return primeSum;
}

namespace GiovaProblem11
{

	inline const int* getElementAtDir(const int* curPosition, UInt direction)
	{
		switch(direction)
		{
		case 0: return curPosition + 1;
		case 1: return curPosition + 20;
		case 2: return curPosition + 21;
		case 3: return curPosition + 19;
		default: assert(false); return 0;
		}
	}

	inline UInt32 calculateMul(const int* curPosition, UInt direction)
	{
		UInt32 result = *curPosition;
		//const int* tempPtr = curPosition;

		for(UInt i = 0; i < 3; ++i)
		{
			curPosition = getElementAtDir(curPosition, direction);
			result *= *curPosition;
		}

		return result;
	}

}

/*

In the 20x20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26  63  78  14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20x20 grid?

*/
RetType MartinoGiovanelli::Problem11()
{
	// wtf: i spent only 10min to add commas and transform the format '0x' to 'x' ...
	//ugasoft: asd... thank you! I moved them in ProblemCommons for everyone else use!
	
	int i = 0;
	int curMaxMul = 0;
	int tempMul1, tempMul2 = 0;
	const int* const buffer = problem_data::problem11numbers;

	while(i < 397)
	{
		// right
		tempMul1 = GiovaProblem11::calculateMul(buffer + i, 0);

		if(i < 340)
		{
			// down
			tempMul2 = GiovaProblem11::calculateMul(buffer + i, 1);
			if(tempMul2 > tempMul1)
				tempMul1 = tempMul2;

			if(i == 0 || 400 % i < 17)
			{
				// diagonal 1
				tempMul2 = GiovaProblem11::calculateMul(buffer + i, 2);
				if(tempMul2 > tempMul1)
					tempMul1 = tempMul2;
			}
			if(i == 0 || 400 % i > 2)
			{
				// diagonal 2
				tempMul2 = GiovaProblem11::calculateMul(buffer + i, 3);
				if(tempMul2 > tempMul1)
					tempMul1 = tempMul2;
			}
		}

		if(tempMul1 > curMaxMul)
			curMaxMul = tempMul1;

		++i;
	}

	return curMaxMul;
}

RetType MartinoGiovanelli::Problem12()
{

	RetType currentNum = 0; 
	RetType tempNum = 0;
	RetType currentI = 0;
	RetType currentDiv = 0;
	RetType contoVero = 1;
	bool check = false;
	UInt32 divisor = 2;

	/*
Essentially it boils down to if your number n = a^x * b^y * c^z
(where a, b, and c are n's prime divisors and x, y, and z are the number of times that divisor is repeated)
then the total count for all of the divisors is (x + 1) * (y + 1) * (z + 1).
	*/
	do
	{
		currentNum += ++currentI;

		currentDiv = 0;

		divisor = 2;
		tempNum = currentNum;
		contoVero = 1;

		do
		{
			if (tempNum % divisor == 0)
			{
				tempNum /= divisor;
				++currentDiv;
				check = true;
			}
			else
			{
				if(check)
				{
					contoVero *= ++currentDiv;
					currentDiv = 0;
					check = false;
					tempNum = currentNum;
				}

				do 
				{
					++divisor;
				}
				while (!math::IsPrime(divisor));
				
			}
		}
		while (/*tempNum != 1 &&*/ divisor <= tempNum);

	}while (contoVero <= 500);

	return currentNum;
}

/*
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
*/
RetType MartinoGiovanelli::Problem13()
{
	GiovaMath::BigNumber sum = GiovaMath::BigNumber(problem_data::problem13numbers[0]);

	for (UInt i = 1; i < 100; ++i)
	{
		sum += GiovaMath::BigNumber(problem_data::problem13numbers[i]);
	}
	return sum.toInt64(sum.getDigitNum() - 10);
}

/*
The following iterative sequence is defined for the set of positive integers:

n  n/2 (n is even)
n  3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13  40  20  10  5  16  8  4  2  1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.
*/
RetType MartinoGiovanelli::Problem14()
{
	UInt32 bestNum = 0;
	UInt32 bestCount = 0;
	UInt32 tempNum = 0;
	UInt32 count = 0;

	for(Int32 i = 1000000; i > 1; --i)
	{
		tempNum = i;

		do 
		{
			if(math::IsOdd(tempNum))	tempNum = 3 * tempNum + 1;
			else						tempNum >>= 1;

			++count;

		} while (tempNum > 1);

		if(count > bestCount)
		{
			bestNum = i;
			bestCount = count;
		}

		count = 0;
	}

	return bestNum;
}

/*
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?
*/
RetType MartinoGiovanelli::Problem16()
{
	GiovaMath::BigNumber sum = GiovaMath::BigNumber(static_cast<UInt64>(2));

	for (Int32 i = 1000; i > 1; --i)
	{
		sum += sum;
	}

	RetType result = 0;
	
	for(UInt32 i = 0; i < sum.getDigitNum(); ++i)
		result += sum.getDigitAt(i);

	return result;
}

/*
n! means n x (n -  1)  ...  3 x 2 x 1

Find the sum of the digits in the number 100!
*/
RetType MartinoGiovanelli::Problem20()
{
	GiovaMath::BigNumber sum = GiovaMath::BigNumber(static_cast<UInt64>(100));

	for(UInt32 i = 99; i > 1; --i)
	{
		sum *= i;
	}

	RetType result = 0;

	for(UInt32 i = 0; i < sum.getDigitNum(); ++i)
		result += sum.getDigitAt(i);

	return result;
}

/*
The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?
*/
RetType MartinoGiovanelli::Problem25()
{
	using namespace GiovaMath;

	RetType i = 2;

	BigNumber n;
	BigNumber n1 = BigNumber(1u);
	BigNumber n2 = BigNumber(2u);

	do 
	{
		n = n1 + n2;
		n2 = n1;
		n1 = n;

		++i;

	} while (n.getDigitNum() < 1000);

	return i;
}

/*
The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
*/
RetType MartinoGiovanelli::Problem48()
{
	GiovaMath::BigNumber sum;
	GiovaMath::BigNumber pSum;

	for(UInt32 i = 1; i <= 1000; ++i)
	{
		pSum = GiovaMath::BigNumber(static_cast<UInt64>(i));

		for (UInt32 j = 1; j < i; ++j)
		{
			pSum *= i;
		}

		sum += pSum;
	}

	return sum.toInt64(sum.getDigitNum() - 10);
}